class Solution {
public:
    bool isPowerOfThree(int n) {
        if(n==1) return true;
        if(n==0) return false;
        if(n%3!=0){
          return false;
        }else if(n%3==0&&n==9){
          return true;
        }else{
          n=n/3;
          return isPowerOfThree(n);
        }
    }
};
